﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.ComponentModel;
using ClearingRestartingAutomaton.Common;

namespace ClearingRestartingAutomaton.Base
{
    /// <summary>
    /// The AutomatonInference class represents the core class for inferring minimal
    /// clearing restarting automaton based on positive and negative samples.
    /// </summary>
    [Serializable]
    public class AutomatonInference
    {
        #region Constructors

        /// <summary>
        /// Default constructor of this class.
        /// </summary>
        public AutomatonInference()
        {

        }

        #endregion

        #region Public Properties

        /// <summary>
        /// Gets the list of positive samples.
        /// </summary>
        public List<string> PositiveSamples
        {
            get { return this.positiveSamples; }
        }

        /// <summary>
        /// Gets the list of negative samples.
        /// </summary>
        public List<string> NegativeSamples
        {
            get { return this.negativeSamples; }
        }

        /// <summary>
        /// Gets the list of enabled to-words.
        /// </summary>
        public List<string> ToWords
        {
            get { return this.toWords; }
        }

        #endregion

        #region Public Methods

        /// <summary>
        /// Returns the Automaton consistent with the given positive and negative samples having 
        /// the specified maximal width of instructions, length of contexts and maximal number of rules.
        /// Returns null if no such automaton exists.
        /// </summary>
        /// <param name="maximalWidth">Maximal instruction width.</param>
        /// <param name="contextLength">Length of contexts.</param>
        /// <param name="maximalRuleCount">Maximal number of rules.</param>
        /// <param name="enableDeltaRules">Enable delta rules.</param>
        /// <param name="backgroudWorker">Background worker.</param>
        /// <returns>
        /// The instance of the Automaton class consistent with the given positive and negative samples 
        /// having the specified maximal width of instructions, length of contexts and maximal number of rules,
        /// or null if no such automaton exists.
        /// </returns>
        public Automaton GetAutomaton(int maximalWidth, int contextLength, int maximalRuleCount, bool enableDeltaRules, BackgroundWorker backgroudWorker)
        {
            if (enableDeltaRules)
            {
                this.toWords = new List<string>() { String.Empty, "#" };
            }
            else
            {
                this.toWords = new List<string>() { String.Empty };
            }
            this.forbiddenInstructions.Clear();
            return this.GetAutomaton(new Automaton(), maximalWidth, contextLength, maximalRuleCount, backgroudWorker);
        }

        #endregion

        #region Private Methods

        /// <summary>
        /// Returns the Automaton consistent with the given positive and negative samples having 
        /// the specified maximal width of instructions, length of contexts and maximal number of rules.
        /// Returns null if no such automaton exists.
        /// </summary>
        /// <param name="partialAutomaton">Partial automaton constructed so far.</param>
        /// <param name="maximalWidth">Maximal instruction width.</param>
        /// <param name="contextLength">Length of contexts.</param>
        /// <param name="maximalRuleCount">Maximal number of rules.</param>
        /// <param name="backgroudWorker">Background worker.</param>
        /// <returns>
        /// The instance of the Automaton class consistent with the given positive and negative samples 
        /// having the specified maximal width of instructions, length of contexts and maximal number of rules,
        /// or null if no such automaton exists.
        /// </returns>
        private Automaton GetAutomaton(Automaton partialAutomaton, int maximalWidth, int contextLength, int maximalRuleCount, BackgroundWorker backgroudWorker)
        {
            if (backgroudWorker != null && backgroudWorker.CancellationPending)
            {
                return null;
            }

            InstructionCollection partialInstructionCollection = 
                new InstructionCollection(partialAutomaton.Instructions);

            foreach (InstructionCollection instructionCollection in this.forbiddenInstructions)
            {
                if (instructionCollection.IsSubset(partialInstructionCollection))
                {
                    return null;
                }
            }

            WordForest negativeClosure = partialAutomaton.MakeWordForest(
                this.negativeSamples,
                StringDefaultValues.LeftDelimiter,
                StringDefaultValues.RightDelimiter,
                InstructionUse.Reduction, 0, 0);

            if (negativeClosure.ForestSet.ContainsKey(String.Empty) ||
                this.positiveSamples.Any(sample => negativeClosure.ForestSet.ContainsKey(sample)))
            {
                this.forbiddenInstructions.Add(partialInstructionCollection);

                if (backgroudWorker != null)
                {
                    backgroudWorker.ReportProgress(0, String.Join(", ", partialInstructionCollection.Instructions.Select(i => i.ToString())));
                }

                return null;
            }

            WordForest positiveClosure = partialAutomaton.MakeWordForest(
                this.positiveSamples, 
                StringDefaultValues.LeftDelimiter,
                StringDefaultValues.RightDelimiter,
                InstructionUse.Reduction, 0, 0);

            // We mark all the words in the wordForest structure that are reducible to the empty word.
            if (positiveClosure.ForestSet.ContainsKey(String.Empty))
            {
                Queue<string> Q = new Queue<string>();
                positiveClosure.ForestSet[String.Empty] = 1;
                Q.Enqueue(String.Empty);
                while (Q.Count > 0)
                {
                    string actualWord = Q.Dequeue();
                    if (positiveClosure.ForestSteps.ContainsKey(actualWord))
                    {
                        foreach (string word in positiveClosure.ForestSteps[actualWord].Select(s => s.Word))
                        {
                            if (positiveClosure.ForestSet.ContainsKey(word) && positiveClosure.ForestSet[word] == 0)
                            {
                                positiveClosure.ForestSet[word] = 1;
                                Q.Enqueue(word);
                            }
                        }
                    }
                }
            }

            // We find all unresolved words in the wordForest structure (i.e. words that are not reducible to the empty word).
            List<string> unresolvedSamples = new List<string>();
            foreach (KeyValuePair<string, int> pair in positiveClosure.ForestSet)
            {
                if (pair.Value == 2)
                {
                    unresolvedSamples.Add(pair.Key);
                }
            }

            if (unresolvedSamples.Count == 0)
            {
                return partialAutomaton;
            }
            else
            {
                unresolvedSamples.Sort((a, b) => a.LengthLexCompare(b));

                SortedDictionary<string, bool> automatonRules = 
                    new SortedDictionary<string, bool>(new StringLengthLexComparer());
                foreach (Instruction instruction in partialAutomaton.Instructions)
                {
                    automatonRules[instruction.FromWord] = true;
                }
                bool isAutomatonFull = (maximalRuleCount > 0 && automatonRules.Count == maximalRuleCount);

                SortedDictionary<Instruction, bool> instructionCandidates = new SortedDictionary<Instruction, bool>();

                foreach (string unresolvedWord in unresolvedSamples)
                {
                    string delimitedUnresolvedWord = StringDefaultValues.LeftDelimiter + unresolvedWord + StringDefaultValues.RightDelimiter;
                    for (int width = 1; width <= Math.Min(maximalWidth, unresolvedWord.Length); ++width)
                    {
                        for (int index = 0; index <= unresolvedWord.Length - width; ++index)
                        {
                            string fromWord = unresolvedWord.Substring(index, width);
                            if (isAutomatonFull && !automatonRules.ContainsKey(fromWord))
                            {
                                continue;
                            }
                            int contextIndex = StringDefaultValues.LeftDelimiter.Length + index;
                            string leftContext = String.Empty;
                            string rightContext = String.Empty;
                            if (contextLength > 0)
                            {
                                int leftContextStart = Math.Max(0, contextIndex - contextLength);
                                leftContext = delimitedUnresolvedWord.Substring(leftContextStart, contextIndex - leftContextStart);
                                int rightContextEnd = Math.Min(delimitedUnresolvedWord.Length, contextIndex + width + contextLength);
                                rightContext = delimitedUnresolvedWord.Substring(contextIndex + width, rightContextEnd - contextIndex - width);
                            }
                            if (leftContext.Length + width + rightContext.Length <= maximalWidth)
                            {
                                foreach (string toWord in this.toWords)
                                {
                                    instructionCandidates[new Instruction(leftContext, fromWord, toWord, rightContext)] = true;
                                }
                            }
                            else break;
                        }
                    }
                }

                foreach (Instruction instruction in instructionCandidates.Keys)
                {
                    if (!partialAutomaton.Instructions.Contains(instruction))
                    {
                        WordTree instructionClosure = partialAutomaton.MakeWordTree(
                            instruction.FromWord,
                            instruction.LeftContext,
                            instruction.RightContext,
                            InstructionUse.Reduction, 0, 0);
                        if (!instructionClosure.TreeSet.ContainsKey(instruction.ToWord))
                        {
                            partialAutomaton.Instructions.Add(instruction);
                            Automaton automaton = this.GetAutomaton(partialAutomaton, maximalWidth, contextLength, maximalRuleCount, backgroudWorker);
                            if (automaton != null)
                            {
                                return automaton;
                            }
                            partialAutomaton.Instructions.RemoveAt(partialAutomaton.Instructions.Count - 1);
                        }
                    }
                }

                return null;
            }
        }

        #endregion

        #region Private Data Members

        private List<string> positiveSamples = new List<string>();
        private List<string> negativeSamples = new List<string>();
        private List<string> toWords = new List<string>() { String.Empty };
        private List<InstructionCollection> forbiddenInstructions = new List<InstructionCollection>();

        #endregion
    }
}
